//
// Created by lyc on 2025/3/9.
//
#include<iostream>
#include<vector>
using namespace std;

bool isSafe(int row, int col, vector<int> Queens){
    /*
     * func: 判断当前落子位置是否安全
     * param: 当前落子行和列, 已落子序列Queens, 元素值表示列, 下标表示行
     * out: false ->不安全     true ->安全
     */

    for(int i = 1; i <= Queens.size(); i++){
        if(Queens[i-1] == col || abs(i - row) == abs(col - Queens[i-1])){
            return false;
        }
    }

    return true;
}

int count_ways = 0;

void algorithm9(int row, vector<int>& Queens){
    /*
     * func: 递归方法实现八皇后问题, 抓住一点: 每行一定要放一个棋子。 以行为参数, 内部对
     *       列进行遍历, 找到能落子的位置, 若找不到, 说明之前的落子位置不对, 进行回退直到能
     *       找到全部落子位置
     * param: 当前行, 已经落子序列
     *
     */

    if(row > 8){
        /*
         * 如果已经遍历到了第9行, 说明前8行已经确定, 已经找到一种可行的方法
         */
        count_ways++;
        return;
    }

    for(int col = 1; col <= 8; col++){
        if(isSafe(row, col, Queens)){
            /*
             * 若安全, 在此处落子
             */
            Queens.push_back(col);
            algorithm9(row + 1, Queens);

            /*
             * 若row+1的情况下找不到安全位置, 则会返回运行到这里, 说明这个位置可能不对, 需要退回重新遍历
             * ***
             * 回退这一步很关键, 位置和操作都要掌控好
             */
            Queens.pop_back();
        }
    }



}


